/*
 * @lc app=leetcode.cn id=1005 lang=javascript
 *
 * [1005] K 次取反后最大化的数组和
 */

// @lc code=start
/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number}
 */
var largestSumAfterKNegations = function (nums, k) {
  const sorted = nums.sort((a, b) => a - b);

  for (let i = 0; i < k; i++) {
    const num = sorted[i];
    if (num <= 0) {
      sorted[i] = -num;
    } else {
      const remain = k - i;

      if (remain % 2 === 0) {
        break;
      } else {
        // 找到最小正数的下标
        if (i == 0 || sorted[i] < sorted[i - 1]) {
          sorted[i] = -sorted[i];
        } else {
          sorted[i - 1] = -sorted[i - 1];
        }

        break;
      }
    }
  }

  return sorted.reduce((a, b) => a + b, 0);
};
// @lc code=end

// @after-stub-for-debug-begin
module.exports = largestSumAfterKNegations;
// @after-stub-for-debug-end
